package com.lanluo.service.sort;

/**
 * 插入排序
 * 1.将数组分为两部分,第一部分1个元素,第二部分n-1个元素
 * 2.从第二部分中取元素插入第一部分,并依次比较交换
 * @author
 * @date 2018-08-27-18:01
 */
public class Insertion extends Example{
    public static void sort(Comparable[] a) {
        int N = a.length;
        for (int i = 1; i < N; i++) {
            //将a[i]插入到a[i-1]、a[i-2]、..中
            for(int j=i; j>0&&less(a[j], a[j-1]); j--) {
                exch(a, j,j-1);
            }
        }
    }

    public static void main(String[] args) {
        String[] a = {"D", "B", "A", "C"};
        sort(a);
        System.out.println(isSorted(a));
        show(a);
    }

}